package com.sourcetrip.algorithm.unionfind;

import com.sourcetrip.algorithm.abs.AbstractUnionFind;

/**
 * @author: ZhouBert
 * @date: 2021/1/5
 * @description: 并查集（以 Quick Find 的思路实现）
 * --
 * 设计：
 * 1.数组中每个元素都是指向自己的根节点，而且最多只能有两层（一棵多叉树，而且根节点指向自身）
 * --
 * 分析：
 * 1.find(int):int 的时间复杂度：O(1);
 * 2,union(int,int):void 的时间复杂度是：O(n)
 */
public class UnionFindWithQuickFind extends AbstractUnionFind {
	/**
	 * 构建固定容量的并查集
	 * 默认初始 parents 的元素的根节点指向自身，这样表示每个元素都是独立的集合
	 *
	 * @param capacity 并查集的容量
	 */
	public UnionFindWithQuickFind(int capacity) {
		super(capacity);
	}

	/**
	 * 返回 v 所属的集合
	 *
	 * @param v
	 * @return
	 */
	@Override
	public int find(int v) {
		rangeCheck(v);
		return parents[v];
	}

	/**
	 * 将 v1 和 v2 合并到统一集合（按照 v2 的根节点）
	 * （原理是通过左边所有节点进行依附到右边的根节点，保证了树的高度 max=2）
	 *
	 * @param v1
	 * @param v2
	 */
	@Override
	public void union(int v1, int v2) {
		int s1 = find(v1);
		int s2 = find(v2);
		//如果已经是同一个集合了，就不做处理
		if (s1 == s2) {
			return;
		}

		for (int i = 0; i < parents.length; i++) {
			//这里写的时候注意不要写成 parents[v1] 了！因为是会变的！
			if (parents[i] == s1) {
				parents[i] = s2;
			}
		}
	}
}
